Thuật toán BLAST

Ý tưởng của BLAST dựa trên cơ sở xác suất rằng những chuỗi bắt cặp trình tự (alignment) thường sở hữu nhiều đoạn chuỗi con có tính tương tự cao. Những chuỗi con này được mở rộng để tăng tính tương tự trong quá trình tìm kiếm.

Thuật toán của BLAST có 2 phần, một phần tìm kiếm và một phần đánh giá thống kê dựa trên kết quả tìm được.

Thuật toán tìm kiếm của BLAST bao gồm 3 bước sau:

  • Bước 1: BLAST tìm kiếm các chuỗi con ngắn với chiều dài cố định W có tính tương tự cao (không cho phép khoảng trống gaps) giữa chuỗi truy vấn và các chuỗi trong cơ sở dữ liệu.
    Những chuỗi con với chiều dài W được BLAST gọi là một từ (word).
    Giá trị W tham khảo cho Protein là 3 và DNA là 11.
    Những chuỗi con này được đánh giá cho điểm dựa trên ma trận thay thế (Substitutionsmatrix) BLOSUM hoặc PAM, những chuỗi con nào có số điểm lớn hơn một giá trị ngưỡng T (threshold value) thì được gọi là tìm thấy và được BLAST gọi là Hits.
    Ví dụ, khi cho sẵn các chuỗi AGTTAH và ACFTAQ và một từ có chiều dài W = 3, BLAST sẽ xác định chuỗi con TAH và TAQ với số điểm theo ma trận PAM là 3 + 2 + 3 = 8 và gọi chúng là một Hit.
  • Bước 2: BLAST tiếp tục tìm kiếp những cặp Hits tiếp theo dựa trên cơ sở những Hit đã tìm được trong bước 1. Những cặp Hits này được BLAST giới hạn bởi một giá trị cho trước d, gọi là khoảng cách giữa những Hits. Những cặp Hits có khoảng cách lớn hơn d sẽ bị BLAST bỏ qua.
    Giá trị d phụ thuộc vào độ dài W ở bước 1, ví dụ nếu W = 2 thì giá trị d đề nghị là d = 16.
  • Bước 3: Cuối cùng BLAST mở rộng những cặp Hits đã tìm được theo cả hai chiều và đồng thời đánh số điểm. Quá trình mở rộng kết thúc khi điểm của các cặp Hits không thể mở rộng thêm nữa.
    Một điểm chú ý ở đây là phiên bản gốc của BLAST không cho phép chỗ trống (gap) trong quá trình mở rộng, nhưng ở phiên bản mới hơn đã cho phép chỗ trống.
    Những cặp Hits sau khi mở rộng có điểm số cao hơn một giá trị ngưỡng S (threshold value) thì được BLAST gọi là "cặp điểm số cao" (high scoring pair) HSP.
    Ví dụ, với chuỗi AGTTAHTQ và ACFTAQAC với Hit TAH và TAQ sẽ được mở rộng như sau:

AGTTAHTQ
xxx||||x
ACFTAQAC

Những cặp HSP đã tìm được được BLAST sắp xếp theo giá trị đánh giá giảm dần, đưa ra màn hình, và thực hiện phần đánh giá thống kê trên những cặp HSP này.

Trong phần đánh giá thống kê, BLAST dựa trên cơ sở đánh giá của một cặp HSP để tính ra một giá trị gọi là ''Bit-Score'', giá trị này không phụ thuộc vào ma trận thay thế và được sử dụng để đánh giá chất lượng của các bắt cặp. Giá trị càng cao chứng tỏ khả năng tương tựu của các bắt cặp càng cao.Ngoài ra BLAST tính toán một giá trị trông đợi E-Score (Expect-Score) phụ thuộc vào Bit-Score. Giá trị E-Score này thể hiện xác suất ngẫu nhiên của các bắt cặp, giá trị càng thấp càng chứng tỏ những bắt cặp này được phát sinh theo quy luật tự nhiên, ít phụ thuộc vào tính ngẫu nhiên. (Xem thêm về đột biến (Mutation)).

Liên quan